package Seven_sorts.Leetcode;

/**
 * 数组中的逆序对
 */
public class jianzhiOffer51_reversePairs {
    public int reversePairs(int[] nums){
        return reversePairsInternal(nums,0,nums.length-1);
    }

    /**
     * 在nums[l...r]上进行归并排序，返回排序后的逆序对
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private int reversePairsInternal(int[] nums, int l, int r) {
        //此时数组为空或者数组只有一个元素
        if (l>=r){
              return 0;
          }
        int mid=l+(r-l)/2;
        //先求出第一个子数组的逆序对个数
        int leftCount=reversePairsInternal(nums,l,mid);
        //在求出第二个子数组的逆序对个数
        int rightCount=reversePairsInternal(nums,mid+1,r);
        if (nums[mid]>nums[mid+1]){
            //此时左右数组有序，但是这两个数组之间还存在逆序，再求出合并过程的逆序对
            return leftCount+rightCount+merge(nums,l,mid,r);
        }
        //nums[mid]<nums[mid+1],说明此时整个数组已经有序，就没有逆序对存在了
        return leftCount+rightCount;
    }

    /**
     * 合并两个有序的组数组nums[l...mid]和nums[mid+1]，返回和并购的逆序对个数
     * @param nums
     * @param l
     * @param mid
     * @param r
     * @return
     */
    private int merge(int[] nums, int l, int mid, int r) {
        //合并后产生的逆序对个数
        int count=0;
        int temp[] =new int[r-l+1];
        for (int i = l; i <=r; i++) {
            temp[i-l]=nums[i];
        }
        int i=l,j=mid+1;
        for (int k = l; k <=r; k++) {
            if (i>mid){
                //第一个数组已经处理完毕，直接拼接第二个数组，此时没有逆序对
                nums[k]=temp[j-l];
                j++;
            } else if (j>r) {
                //第二个数组已经处理完毕，直接拼接第一个数组，此时没有逆序对
                nums[k]=temp[i-l];
                i++;
            } else if (temp[i-l]<=temp[j-l]) {
                nums[k]=temp[i-l];
                i++;
            }else {
                //此时第一个数组元素>第二个数组元素，从i开始到mid结束的所有元素相较于arr[j]都是逆序对
                //逆序对个数为mid-i+1
                count+=mid-i+1;
                nums[k]=temp[j-l];
                j++;
            }
        }
        return count;
    }

}
